|
PL, or probabilistic L, is the class of languages recognizable by a polynomial time logarithmic space randomized machine with probability > 1/2 (this is called unbounded error). Equivalently, as shown below, PL is the class of languages recognized by unbounded time unbounded error logspace randomized machine. An example of PL complete problem (under logspace reduction) is finding whether the determinant of a matrix (with integral coefficients) is positive. Given a matrix M and a number n, testing with |M|>n is also PL complete. By contrast, testing whether matrix permanent is positive is PP complete. PLPL=PL in the sense that for every f in PL, PL is unchanged if it is extended to allow x→f(A,x) as a subroutine, where A is the input string. PL contains NL and BPL and is contained in NC2. == Approximating determinant in PL == Determinant of an integral matrix can be reduced to finding the difference between the number of accepting and rejecting paths on a polynomially sized directed acyclic graph with distinguished start, accept, and reject nodes. Comparing the number of accepting and rejecting paths can be done in PL as follows. Modify the graph to make all paths the same length and for each node to have at most two successors. Take a random path. For each node with just one successor, fail (output random answer) with probability 1/2. At the end, accept if we reached Accept node, reject if we reached Reject node, and fail otherwise. Each distinct path will be counted equally — while some paths are more likely to be taken, this is exactly compensated by reduced likelihood of continuing along that path. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「PL (complexity)」の詳細全文を読む スポンサード リンク
|